Disclosed herein is a method and associated devices, for Low-Density Parity Check (LDPC) decoding, that overcome non-convergence due to trapping sets.
Error Correction Codes (ECCs) are commonly used in communication systems and in storage systems. Various physical phenomena occurring both in communication channels and in storage devices result in noise effects that corrupt the communicated or stored information. Error correction coding schemes can be used for protecting the communicated or stored information against the resulting errors. This is done by encoding the information before transmission through the communication channel or storage in the memory device. The encoding process transforms the information bits sequence into a codeword by adding redundancy to the information. This redundancy can then be used in order to recover the information from the possibly corrupted codeword through a decoding process.
In both communication systems and storage systems an information bit sequence i is encoded into a coded bit sequence v that is modulated or mapped into a sequence of symbols x that is adapted to the communication channel or to the memory device. At the output of the communication channel or memory device a sequence of symbols y is obtained. An ECC decoder of the system decodes the sequence y and recovers the bit sequence {circumflex over (i)}, which should reconstruct the original information bit sequence i with high probability.
A common ECC family is the family of linear binary block codes. A length N linear binary block code of dimension K is a linear mapping of length K information bit sequences into length N codewords, where N>K. The rate of the code is defined as R=K/N. The encoding process of a codeword v of dimension 1×N is usually done by multiplying the information bits sequence i of dimension 1×K by a generator matrix C of dimension K×N and rank K according tov=i·G   (1)It is also customary to define a parity-check matrix H of dimension M×N and rank M, where M=N−K. The parity-check matrix is related to the generator matrix through the following equation:GHT=0   (2)The parity-check matrix can be used in order to check whether a length N binary vector is a valid codeword. A 1×N binary vector v belongs to the code if and only if the following equation holds:H·v′=0   (3)(In equation (3), the prime on v′ means that v′ is a column vector.)
In recent years iterative coding schemes have become very popular. In these schemes the code is constructed as a concatenation of several simple constituent codes and is decoded using an iterative decoding algorithm by exchanging information between the constituent decoders of the simple codes. Usually, the code can be defined using a bipartite graph describing the interconnections between the constituent codes. In this case, decoding can be viewed as an iterative message passing over the graph edges.
A popular class of iterative codes is Low-Density Parity-Check (LDPC) codes. An LDPC code is a linear binary block code defined by a sparse parity-check matrix H. As shown in FIG. 1, the code can be defined equivalently by a sparse bipartite “(Tanner” graph G=(V,C,E) with a set V of N bit nodes (N=13 in FIG. 1), a set C of M check nodes (M=10 in FIG. 1) and a set E of edges (F=38 in FIG. 1) connecting bit nodes to check nodes. The bit nodes correspond to the codeword bits and the check nodes correspond to parity-check constraints on the bits. A bit node is connected by edges to the check nodes that the bit node participates with. In the matrix representation of the code on the left side of FIG. 1 an edge connecting bit node i with check node j is depicted by a non-zero matrix element at the intersection of row j and column i.
Next to the first and last check nodes of FIG. 1 are shown the equivalent rows of equation (3). The symbol “⊕” means “XOR”.
LDPC codes can be decoded using iterative message passing decoding algorithms. These algorithms operate by exchanging messages between bit nodes and check nodes along the edges of the underlying bipartite graph that represents the code. The decoder is provided with initial estimates of the codeword bits (based on the communication channel output or based on the read memory content). These initial estimates are refined and improved by imposing the parity-check constraints that the bits should satisfy as a valid codeword (according to equation (3)). This is done by exchanging information between the bit nodes representing the codeword bits and the check nodes representing parity-check constraints on the codeword bits, using the messages that are passed along the graph edges.
In iterative decoding algorithms, it is common to utilize “soft” bit estimations, which convey both the bit estimations and the reliabilities of the bit estimations.
The bit estimations conveyed by the messages passed along the graph edges can be expressed in various forms. A common measure for expressing a “soft” bit estimation is as a Log-Likelihood Ratio (LLR)
      log    ⁢                  Pr        ⁡                  (                      v            =                          0              |                              current                ⁢                                                                  ⁢                constraints                ⁢                                                                                          ⁢                                                                                        ⁢                and                ⁢                                                                  ⁢                observations                                              )                            Pr        ⁡                  (                      v            =                          1              |                              current                ⁢                                                                  ⁢                constraints                ⁢                                                                                          ⁢                                                                                        ⁢                and                ⁢                                                                  ⁢                observations                                              )                      ,where the “current constraints and observations” are the various parity-check constraints taken into account in computing the message at hand and the observations y corresponding to the bits participating in these parity checks. Without loss of generality, for simplicity we assume hereinafter that LLR messages are used throughout. The sign of the LLR provides the bit estimation (i.e., positive LLR corresponds to v=0 and negative LLR corresponds to v=1). The magnitude of the LLR provides the reliability of the estimation (i.e. |LLR|=0 means that the estimation is completely unreliable and |LLR|=∞ means that the estimation is thought to be completely reliable and the bit value is thought to be known).
Usually, the messages passed during the decoding along the graph edges between bit nodes and check nodes are extrinsic. An extrinsic message m passed from a node n on an edge e takes into account all the values received on edges connected to n other than edge e (this is why the message is called extrinsic: it is based only on new information).
One example of a message passing decoding algorithm is the Belief-Propagation (BP) algorithm, which is considered to be the best algorithm from among this family of message passing algorithms.
Let
      P    v    =      log    ⁢                  Pr        ⁡                  (                      v            =                          0              |              y                                )                            Pr        ⁡                  (                      v            =                          1              |              y                                )                    denote the initial decoder estimation for bit v, based only on the received or read symbol y. Note that it is also possible that some of the bits are not transmitted through the communication channel or stored in the memory device, hence there is no y observation for these bits. In this case, there are two possibilities: 1) shortened bits—the bits are known a-priori and Pv=±∞ (depending on whether the bit is 0 or 1). 2) punctured bits—the bits are unknown a-priori and
            P      v        =          log      ⁢                        Pr          ⁡                      (                          v              =              0                        )                                    Pr          ⁡                      (                          v              =              1                        )                                ,where Pr(v=0) and Pr(v=1) are the a-priori probabilities that the bit v is 0 or 1 respectively. Assuming the information bits have equal a-priori probabilities to be 0 or 1 and assuming the code is linear then
      P    v    =            log      ⁢                        1          /          2                          1          /          2                      =    0.  
Let
      Q    v    =      log    ⁢                  Pr        ⁡                  (                                    v              =                              0                |                                  y                  _                                                      ,                                          H                ·                                  v                  _                                            =              0                                )                            Pr        ⁡                  (                                    v              =                              1                |                                  y                  _                                                      ,                                          H                ·                                  v                  _                                            =              0                                )                    denote the final decoder estimation for bit v, based on the entire received or read sequence y and assuming that bit v is part of a codeword (i.e., assuming H·v=0).
Let Qvc denote a message from bit node V to check node c. Let Rcv denote a message from check node c to bit node v.
The BP algorithm utilizes the following update rules for computing the messages:
The bit node to check node computation rule is:
                              Q          vc                =                              P            v                    +                                    ∑                                                c                  ′                                ∈                                                      N                    ⁡                                          (                                              v                        ,                        G                                            )                                                        ⁢                  \                  ⁢                  c                                                      ⁢                          R                                                c                  ′                                ⁢                v                                                                        (        4        )            Here, N(n,G) denotes the set of neighbors of a node n in the graph G and c′εN(v,G)\c refers to those neighbors excluding node ‘c’ (the summation is over all neighbors except c).
The check node to bit node computation rule is:
                              R          cv                =                              φ                          -              1                                (                                    ∑                                                v                  ′                                ∈                                                      N                    ⁡                                          (                                              c                        ,                        G                                            )                                                        ⁢                  \                  ⁢                  v                                                      ⁢                                                  ⁢                          φ              ⁡                              (                                  Q                                                            v                      ′                                        ⁢                    c                                                  )                                              )                                    (        5        )            Here
      φ    ⁡          (      x      )        =      {                  sign        ⁢                                  ⁢                  (          x          )                    ,                        -          log                ⁢                                  ⁢                  tanh          ⁡                      (                                                          x                                            2                        )                                }  and operations in the φ domain are done over the group {0,1}×R+ (this basically means that the summation here is defined as summation over the magnitudes and XOR over the signs). Analogous to the notation of equation (4), N(c,G) denotes the set of bit node neighbors of a check node c in the graph G and v′εN(c,G)\v refers to those neighbors excluding node ‘v’ (the summation is over all neighbors except v).
The final decoder estimation for bit v is:
                              Q          v                =                              P            v                    +                                    ∑                                                c                  ′                                ∈                                  N                  ⁡                                      (                                          v                      ,                      G                                        )                                                                        ⁢                          R                                                c                  ′                                ⁢                v                                                                        (        6        )            
The order of passing messages during message passing decoding is called the decoding schedule. BP decoding does not imply utilizing a specific schedule—it only defines the computation rules (equations (4), (5) and (6)). The decoding schedule does not affect the expected error correction capability of the code. However, the decoding schedule can significantly influence the convergence rate of the decoder and the complexity of the decoder.
The standard message-passing schedule for decoding LDPC code is the flooding schedule, in which in each iteration all the variable nodes, and subsequently all the check nodes, pass new messages to their neighbors (R. G. Gallager, Low-Density Parity-Check Codes, Cambridge, Mass.: MIT Press 1963). The standard BP algorithm based on the flooding schedule is given in FIG. 2.
The standard implementation of the BP algorithm based on the flooding schedule is expensive in terms of memory requirements. We need to store a total of 2|V|+2|E| messages (for storing the Pv, Qv, Qvc and Rcv messages). Moreover, the flooding schedule exhibits a low convergence rate and hence requires higher decoding logic (e.g., more processors on an ASIC) for providing a required error correction capability at a given decoding throughput.
More efficient, serial message passing decoding schedules, are known. In a serial message passing schedule, the bit or check nodes are serially traversed and for each node, the corresponding messages are sent into and out from the node. For example, a serial schedule can be implemented by serially traversing the check nodes in the graph in some order and for each check node cεC the following messages are sent:
1. Qvc for each vεN(c) (i.e., all Qvc messages into the node c)
2. Rcv for each vεN(c) (i.e., all Rcv messages from node c)
Serial schedules, in contrast to the flooding schedule, enable immediate and faster propagation of information on the graph resulting in faster convergence (approximately two times faster). Moreover, serial schedule can be efficiently implemented with a significant reduction of memory requirements. This can be achieved by using the Qv messages and the Rcv messages in order to compute the Qvc messages on the fly, thus avoiding the need to use an additional memory for storing the Qvc messages. This is done by expressing Qvc as (Qv−Rcv) based on equations (4) and (6). Furthermore, the same memory as is initialized with the a-priori messages Pv is used for storing the iteratively updated Qv a-posteriori messages. An additional reduction in memory requirements is obtained because in the serial schedule we only need to use the knowledge of N(c) ∀cεC, while in the standard implementation of the flooding schedule we use both data structures N(c) ∀cεC and N(v) ∀vεV requiring twice as much memory for storing the code's graph structure. The serially scheduled decoding algorithm appears in FIG. 3.
To summarize, serial decoding schedules have the following advantages over the flooding schedule:    1) Serial decoding schedules speed up the convergence by a factor of 2 compared to the standard flooding schedule. This means that we need only half the decoder logic in order to provide a given error correction capability at a given throughput, compared to a decoder based on the flooding schedule.    2) Serial decoding schedules provide a memory-efficient implementation of the decoder. A RAM for storing only |V|+|E| messages is needed (instead of for storing 2|V|+2|E| messages as in the standard flooding schedule). Half the ROM size for storing the code's graph structure is needed compared to the standard flooding schedule.    3) “On-the-fly” convergence testing can be implemented as part of the computations done during an iteration, allowing convergence detection during an iteration and decoding termination at any point. This can save on decoding time and energy consumption.Definitions
The methods described herein are applicable to correcting errors in data in at least two different circumstances. One circumstance is that in which data are retrieved from a storage medium. The other circumstance is that in which data are received from a transmission medium. Both a storage medium and a transmission medium are special cases of a “channel” that adds errors to the data. The concepts of “retrieving” and “receiving” data are generalized herein to the concept of “importing” data. Both “retrieving” data and “receiving” data are special cases of “importing” data from a channel.
The data that are decoded by the methods presented herein are a representation of a codeword. The data are only a “representation” of the codeword, and not the codeword itself, because the codeword might have been corrupted by noise in the channel before one of the methods is applied for decoding.
The definition of the second general method described herein requires the definition of “locally homomorphic” rules for modifying values at nodes and at edges and “locally heteromorphic” rules for modifying values at nodes and at edges. A rule is “locally homomorphic” if, starting from the rule for modifying a value associated with a given bit node or with a given check node or with a given edge, if the value(s) associated specifically with that bit node or with that check node or with that edge are swapped for the value(s) specifically associated with a different bit node or check node or edge, then the rule for modifying the corresponding value of the other bit node or check node is obtained. (In the preferred embodiment described below, the values specifically associated with a bit node v are Pv, Sv and the set of messages Qvc and Rcv; the values specifically associated with a check node c are Tc and the set of messages Qvc and Rcv; and the values specifically associated with an edge that connects a bit node v to a check node c are the two messages Qvc and Rcv.) For example, equation (4) is a locally homomorphic rule for replacing the bit-node-to-check-node message value Qvc of one iteration with the Qvc of the next iteration. This rule is locally homomorphic because if the initial estimate value Pv and the check-node-to-bit-node values Rc′v that go into computing Qvc are swapped for the corresponding values associated with a different edge, then the corresponding replacement rule for that edge is obtained. By contrast, in the preferred embodiment described below, the rule for replacing the bit-node-to-check-node message value Qvc of one iteration with the Qvc of the next iteration is either
      Q    vc    =                    P        v            +                        α          e          l                ⁢                              ∑                                          c                ′                            ∈                                                N                  ⁡                                      (                                          v                      ,                      G                                        )                                                  ⁢                \                ⁢                c                                              ⁢                                    R                                                c                  ′                                ⁢                v                                      ⁢                                                  ⁢            or            ⁢                                                  ⁢                          Q              vc                                            =                            α          e          l                ⁡                  (                                    P              v                        +                                          ∑                                                      c                    ′                                    ∈                                                            N                      ⁡                                              (                                                  v                          ,                          G                                                )                                                              ⁢                    \                    ⁢                    c                                                              ⁢                              R                                                      c                    ′                                    ⁢                  v                                                              )                    .      This rule is locally heteromorphic because if the initial estimate value Pv and the check-node-to-bit-node values Rc′v that go into computing Qvc are swapped for the corresponding values associated with a different edge, then the corresponding replacement rule for that edge is not obtained unless the two damping factors αel are coincidentally equal.